package me.mingshan.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
 *
 * @author hanjuntao
 * @date 2025/8/27 0027
 */
public class L_94_二叉树中序遍历 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        //       1
        //      2  3
        //    4   5

        System.out.println(inorderTraversal2(root));  // [4,2,5,1,3]
    }

    /**
     * 中序遍历
     *
     *  对于任意一个二叉树，中序遍历的顺序为：
     *  1. 访问当前节点的左子树；
     *  2. 访问当前节点；
     *  3. 访问当前节点的右子树。
     *
     * @param root
     * @return
     */
    public static List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

        List<Integer> result = new ArrayList<>();

        in(root, result);
        return result;
    }

    public static void in(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }

        in(root.left, result);
        result.add(root.val);
        in(root.right, result);
    }

    /**
     * 递归方式
     *
     * 由于放入栈的顺序与实际遍历的顺序相反
     *
     * 先将左子树放入栈中，然后遍历栈，将栈顶元素出栈，并访问该节点，再遍历该节点的右子树
     *
     * @param root
     * @return
     */
    public static List<Integer> inorderTraversal2(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

        List<Integer> result = new ArrayList<>();

        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                // 根节点入栈
                stack.push(root);
                root = root.left;
            }

            if (stack.isEmpty()) {
                break;
            }

            // 栈不为空，说明有右子树，将栈顶元素出栈，并遍历右子树
            TreeNode pop = stack.pop();
            result.add(pop.val);
            root = pop.right;
        }

        return result;
    }

}
